Baraj pentru lotul olimpic, Bucuresti, mai 1997
Problema 2, Arbori de transmisie (Clara si Eugen Ionescu)
Dificultate: C4-D1

	Ierarhia condorm careia sunt strcuturati angajatii Ministerului
Invatamantului poate fi reprezentata printr-un arbore.
	Atunci cand ministrul doreste sa comunice un mesaj tuturor angajatilor
ministerului, neavand nici o posibilitate de a transmite paralel acest mesaj, 
el recurge la ajutorul subalternilor sai directi care, respectand ierarhia, vor 
transmite mesajul subalternilor directi, s.a.m.d. 
In cazul in care o persoana trebuie sa transmita un mesaj tuturor celor k 
subalterni ai sai, transmiterea va necesita k minute (un minut pentru a transmite 
un mesaj unui subaltern). Nu se "leneveste" inutil, orice persoana transmite 
mesajul mai dparte in minutul imediat urmator receptionarii si lucreaza cat timp
are cui sa transmita. Astfel, pot avea loc mai multe transmisii in paralel (dar
niciodata de la aceeasi persoana in acelasi minut).
	Bineinteles, ministrul ar dori sa stie numarul minim de minute in care
mesajul poate sa ajunga la toti angajatii din minister; de asemenea, el ar dori
sa cunoasca "drumul mesajului". Sunteti rugat sa scrieti un program care rezolva
aceasta problema.
Date de intrare:
	Fisierul de intrare INPUT.TXT contine pe prima linie un numar intreg
N (1<N<=100) reprezentand numarul persoanelor angajate in minister. Pe urmatoarele
n-1 linii se afla cate o pereche de doua numere intregi p1,p2 (1<=p1<=100,
1<=p2<=100), reprezentand doua persoane care sunt in legatura directa.
Date de iesire:
	Rezultatul se va scrie in fisierul de tip text OUTPUT.TXT.
- pe prima linie se va scrie timpul minim necesar t (in minute) pentru a realiza
transmiterea mesajului tuturor angajatilor ministerului. Pe urmatoarele t linii
veti descrie modul de realizare a transmiterii. Ordinea in care specificati o
transmisie intre doua persoane (emitator, receptor) va fi crescatiare dupa emitator.
	Fiecare linie va contine:
- cuvantul 'Minutul';
- apoi un numar intreg reprezentand minutul curent (cuvantul va fi separat de
    numar printr-un blanc);
- urmeaza caracterul ':';
- perechile de persoane intre care are loc transmisia in minutul curent le veti
separa prin virgula si le veti include intre paranteze rotunde; doua perchi de
persoane, incluse intre paranteze se vor separa prin caracterul ';'.
Exemplu:
INPUT.TXT			OUTPUT.TXT
7				4
1 2				Minutul 1: (1,2)
1 3				Minutul 2: (1,3);(2,4)
2 4				Minutul 3: (2,5);(3,6)
2 5				Minutul 4: (3,7)
3 6
3 7

Timp de executie: 5 secunde/test
==============================
	TESTE	
test 1:
9
1 2
1 3
2 4
4 5
4 6
3 7
3 8
8 9
--------------------
test 2:
10
1 2
1 3
2 4
2 5
4 7
4 8
5 9
5 10
3 6
--------------------
test 3:
14
1 2
1 3
2 4
2 5
4 7
4 8
5 9
5 10
3 6
6 11
11 12
12 13
13 14
-----------------------
test 4:
14
1 2
1 3
2 4
2 5
4 6
4 7
5 8
5 9
3 10
3 11
3 12
3 13
3 14
---------------------
test 5:
10
1 2
1 3
2 4
2 5
4 6
5 7
3 8
8 9
9 10
---------------------
test 6:
100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
51 53
51 54
51 55
51 56
51 57
51 58
51 59
51 60
51 61
52 62
52 63
52 64
52 65
52 66
52 67
52 68
52 69
52 70
52 71
53 72
53 73
53 74
53 75
53 76
53 77
53 78
53 79
53 80
53 81
53 82
53 83
53 84
53 85
53 86
53 87
53 88
53 89
53 90
53 91
54 92
55 93
56 94
56 95
57 96
57 97
58 98
59 99
60 100
==============================

Raspunsuri:

test 1:
4
Minutul 1: (1,2)
Minutul 2: (1,3);(2,4)
Minutul 3: (3,8);(4,5)
Minutul 4: (3,7);(4,6);(8,9)
--------------------
test 2:
5
Minutul 1: (1,2)
Minutul 2: (1,3);(2,4)
Minutul 3: (2,5);(3,6);(4,7)
Minutul 4: (4,8);(5,9)
Minutul 5: (5,10)
-------------------
test 3:
6
Minutul 1: (1,3)
Minutul 2: (1,2);(3,6)
Minutul 3: (2,4);(6,11)
Minutul 4: (2,5);(4,7);(11,12)
Minutul 5: (4,8);(5,9);(12,13)
Minutul 6: (5,10);(13,14)
----------------------
test 4:
6
Minutul 1: (1,3)
Minutul 2: (1,2);(3,10)
Minutul 3: (2,4);(3,11)
Minutul 4: (2,5);(3,12);(4,6)
Minutul 5: (3,13);(4,7);(5,8)
Minutul 6: (3,14);(5,9)
----------------------
test 5:
5
Minutul 1: (1,2)
Minutul 2: (1,3);(2,4)
Minutul 3: (2,5);(3,8);(4,6)
Minutul 4: (5,7);(8,9)
Minutul 5: (9,10)
----------------------
test 6:
71
Minutul 1: (1,2)
Minutul 2: (2,3)
Minutul 3: (3,4)
Minutul 4: (4,5)
Minutul 5: (5,6)
Minutul 6: (6,7)
Minutul 7: (7,8)
Minutul 8: (8,9)
Minutul 9: (9,10)
Minutul 10: (10,11)
Minutul 11: (11,12)
Minutul 12: (12,13)
Minutul 13: (13,14)
Minutul 14: (14,15)
Minutul 15: (15,16)
Minutul 16: (16,17)
Minutul 17: (17,18)
Minutul 18: (18,19)
Minutul 19: (19,20)
Minutul 20: (20,21)
Minutul 21: (21,22)
Minutul 22: (22,23)
Minutul 23: (23,24)
Minutul 24: (24,25)
Minutul 25: (25,26)
Minutul 26: (26,27)
Minutul 27: (27,28)
Minutul 28: (28,29)
Minutul 29: (29,30)
Minutul 30: (30,31)
Minutul 31: (31,32)
Minutul 32: (32,33)
Minutul 33: (33,34)
Minutul 34: (34,35)
Minutul 35: (35,36)
Minutul 36: (36,37)
Minutul 37: (37,38)
Minutul 38: (38,39)
Minutul 39: (39,40)
Minutul 40: (40,41)
Minutul 41: (41,42)
Minutul 42: (42,43)
Minutul 43: (43,44)
Minutul 44: (44,45)
Minutul 45: (45,46)
Minutul 46: (46,47)
Minutul 47: (47,48)
Minutul 48: (48,49)
Minutul 49: (49,50)
Minutul 50: (50,51)
Minutul 51: (51,53)
Minutul 52: (51,52);(53,72)
Minutul 53: (51,56);(52,62);(53,73)
Minutul 54: (51,57);(52,63);(53,74);(56,94)
Minutul 55: (51,54);(52,64);(53,75);(56,95);(57,96)
Minutul 56: (51,55);(52,65);(53,76);(54,92);(57,97)
Minutul 57: (51,58);(52,66);(53,77);(55,93)
Minutul 58: (51,59);(52,67);(53,78);(58,98)
Minutul 59: (51,60);(52,68);(53,79);(59,99)
Minutul 60: (51,61);(52,69);(53,80);(60,100)
Minutul 61: (52,70);(53,81)
Minutul 62: (52,71);(53,82)
Minutul 63: (53,83)
Minutul 64: (53,84)
Minutul 65: (53,85)
Minutul 66: (53,86)
Minutul 67: (53,87)
Minutul 68: (53,88)
Minutul 69: (53,89)
Minutul 70: (53,90)
Minutul 71: (53,91)
==============================
